P4035 [JSOI2008]球形空间产生器

发布于 2020-09-05 | 分类于高斯消元 | 3分钟 | 400字数 | 浏览量：

设原形坐标为 $O$ ,圆上一点坐标为 $A$

由提示得：

r=\sqrt{\sum_{i=1}^n(A_i-O_i)^2}

r^2=\sum_{i=1}^n(A_i-O_i)^2

r^2=\sum_{i=1}^n{A_i^2+O_i^2-2A_iO_i}

r^2-\sum_{i=1}^nO_i^2-2A_iO_i=\sum_{i=1}^n{A_i^2}

\sum_{i=1}^n2A_iO_i+(r^2-\sum_{i=1}^nO_i^2)=\sum_{i=1}^n{A_i^2}

括号內的式子与 $A$ 无关，可单独看作一个变量。

因为有 $n+1$ 个点，就有 $n+1$ 组 $A_i$ ，列出 $n+1$ 个方程消元即可。

~~我不会告诉你因为我这题SA打挂了才用的这种方法。~~

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define eps 1e-12

const int MAXN = 10;
int n;
double a[ MAXN + 5 ][ MAXN + 5 ];

void Gauss( ) {
    for( int i = 1 ; i <= n ; i ++ ) {
        int pos = i;
        for( int j = i + 1 ; j <= n ; j ++ )
            if( fabs( a[ j ][ i ] ) > fabs( a[ pos ][ i ] ) ) pos = j;
        swap( a[ pos ] , a[ i ] );
        for( int j = 1 ; j <= n ; j ++ )
            if( i != j ) {
                double t = a[ j ][ i ] / a[ i ][ i ];
                for( int k = i ; k <= n + 1 ; k ++ )
                    a[ j ][ k ] -= t * a[ i ][ k ];
            } 
    }
}

int main( ) {
    scanf("%d",&n); n ++;
    double A;
    for( int i = 1 ; i <= n ; i ++ ) {
    	for( int j = 1 ; j <= n - 1 ; j ++ )
            scanf("%lf",&A) , a[ i ][ j ] = 2 * A , a[ i ][ n + 1 ] += A * A;
        a[ i ][ n ] = 1;
	}
    Gauss( );
    for( int i = 1 ; i <= n - 1 ; i ++ ) printf("%.3f ", a[ i ][ n + 1 ] / a[ i ][ i ] );
    return 0;
}

P4035 [JSOI2008]球形空间产生器

感谢您的支持，我会继续努力的!